package com.android.datastruct;


import java.util.*;

public class ArrayMap<K, V> implements Map<K, V> {
    public static final boolean DEBUG = true;
    public static final String TAG = "";

    static final int[] EMPTY_IMMUTABLE_INTS = new int[0];


    private static final int BASE_SIZE = 4;
    private static final int CACHE_SIZE = 10;
    private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true;
    public static Object[] mBaseCache;
    public static int mBaseCacheSize;
    public static Object[] mTwiceBaseCache;
    public static int mTwiceBaseCacheSize;
    private static final Object sBaseCacheLock = new Object();
    private static final Object sTwiceBaseCacheLock = new Object();

    int[] mHashes;
    Object[] mArray;
    int mSize;


    public ArrayMap(int capacity){
        if (capacity < 0) {
            mHashes = EMPTY_IMMUTABLE_INTS;
            mArray = EmptyArray.OBJECT;
        } else if (capacity == 0) {
            mHashes = EmptyArray.INT;
            mArray = EmptyArray.OBJECT;
        } else {
            allocArrays(capacity);
        }
        mSize = 0;
    }

    private void allocArrays(int size) {
        if (size == (BASE_SIZE*2)) {
            synchronized (sTwiceBaseCacheLock) {
                if (mTwiceBaseCache != null) {
                    final Object[] array = mTwiceBaseCache;
                    mArray = array;
                    try {
                        mTwiceBaseCache = (Object[]) array[0];
                        mHashes = (int[]) array[1];
                        if (mHashes != null) {
                            array[0] = array[1] = null;
                            mTwiceBaseCacheSize--;
                            System.out.println("ArrayMap.allocArrays "+"Retrieving 2x cache " + mHashes
                                    + " now have " + mTwiceBaseCacheSize + " entries");
                            }
                            return;
                    } catch (ClassCastException e) {

                    }
                    // Whoops!  Someone trampled the array (probably due to not protecting
                    // their access with a lock).  Our cache is corrupt; report and give up.
                    System.out.println("ArrayMap.allocArrays "+"Found corrupt ArrayMap cache: [0]=" + array[0]
                            + " [1]=" + array[1]);
                    mTwiceBaseCache = null;
                    mTwiceBaseCacheSize = 0;
                }
            }
        } else if (size == BASE_SIZE) {
            synchronized (sBaseCacheLock) {
                if (mBaseCache != null) {
                    final Object[] array = mBaseCache;

                    mArray = array;
                    System.out.println("ArrayMap.allocArrays in BASE_SIZE,  mArray.length "+mArray.length);

                    try {
                        mBaseCache = (Object[]) array[0];
                        mHashes = (int[]) array[1];
                        System.out.println("ArrayMap.allocArrays  mBaseCache "+mBaseCache);
                        System.out.println("ArrayMap.allocArrays  mHashes "+mHashes[0]);

                        System.out.println("ArrayMap.allocArrays mArray[0]"+mArray[0]);
                        System.out.println("ArrayMap.allocArrays mArray[1]"+mArray[1]);

                        if (mHashes != null) {
                            array[0] = array[1] = null;

                            System.out.println("ArrayMap.allocArrays mArray[0]"+mArray[0]);
                            System.out.println("ArrayMap.allocArrays mArray[1]"+mArray[1]);

                            mBaseCacheSize--;
                            System.out.println("ArrayMap.allocArrays "+"Retrieving 1x cache " + mHashes
                                    + " now have " + mBaseCacheSize + " entries");
                            return;
                        }
                    } catch (ClassCastException e) {
                    }
                    // Whoops!  Someone trampled the array (probably due to not protecting
                    // their access with a lock).  Our cache is corrupt; report and give up.
                    System.out.println("ArrayMap.allocArrays "+"Found corrupt ArrayMap cache: [0]=" + array[0]
                            + " [1]=" + array[1]);
                    mBaseCache = null;
                    mBaseCacheSize = 0;
                }
            }
        }

        mHashes = new int[size];
        mArray = new Object[size<<1];
    }


    @Override
    public int size() {
        return mSize;
    }

    @Override
    public boolean isEmpty() {
        return mSize <= 0;
    }

    @Override
    public boolean containsKey(Object key) {
        return indexOfKey(key) >= 0;
    }

    public int indexOfKey(Object key) {
        return key == null ? indexOfNull()
                : indexOf(key,  key.hashCode());
    }

    private int indexOf(Object key, int hash) {
        System.out.println("ArrayMap.indexOf   "+key+":"+hash);
        final int N = mSize;

        // Important fast case: if nothing is in here, nothing to look for.
        if (N == 0) {
            return ~0;
        }

        int index = binarySearchHashes(mHashes, N, hash);
        System.out.println("ArrayMap.indexOf  after binarySearchHashes "+index);
        // If the hash code wasn't found, then we have no entry for this key.
        if (index < 0) {
            return index;
        }

        // If the key at the returned index matches, that's what we want.
        System.out.println("ArrayMap.indexOf  after key "+key);
        System.out.println("ArrayMap.indexOf  after mArray[index<<1] "+mArray[index<<1]);

        if (key.equals(mArray[index<<1])) {
            return index;
        }

        // Search for a matching key after the index.
        int end;
        for (end = index + 1; end < N && mHashes[end] == hash; end++) {
            System.out.println("444 ArrayMap.indexOf end "+end);
            System.out.println("ArrayMap.indexOf mHashes[end] "+mHashes[end]);
            System.out.println("ArrayMap.indexOf end "+end);

            System.out.println("ArrayMap.indexOf mArray[end << 1] "+mArray[end << 1]);

            if (key.equals(mArray[end << 1])) return end;
        }

        // Search for a matching key before the index.
        for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
            System.out.println("444 ArrayMap.indexOf i "+i);
            System.out.println("ArrayMap.indexOf mHashes[i] "+mHashes[i]);
            System.out.println("ArrayMap.indexOf hash "+hash);

            System.out.println("ArrayMap.indexOf mArray[i << 1] "+mArray[i << 1]);
            if (key.equals(mArray[i << 1])) return i;
        }
        System.out.println("ArrayMap.indexOf ~end "+(~end));
        // Key not found -- return negative value indicating where a
        // new entry for this key should go.  We use the end of the
        // hash chain to reduce the number of array entries that will
        // need to be copied when inserting.
        return ~end;
    }

    private int indexOfNull() {
        final int N = mSize;

        // Important fast case: if nothing is in here, nothing to look for.
        if (N == 0) {
            return ~0;
        }

        int index = binarySearchHashes(mHashes, N, 0);

        // If the hash code wasn't found, then we have no entry for this key.
        if (index < 0) {
            return index;
        }

        // If the key at the returned index matches, that's what we want.
        if (null == mArray[index<<1]) {
            return index;
        }

        // Search for a matching key after the index.
        int end;
        for (end = index + 1; end < N && mHashes[end] == 0; end++) {
            if (null == mArray[end << 1]) return end;
        }

        // Search for a matching key before the index.
        for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
            if (null == mArray[i << 1]) return i;
        }

        // Key not found -- return negative value indicating where a
        // new entry for this key should go.  We use the end of the
        // hash chain to reduce the number of array entries that will
        // need to be copied when inserting.
        return ~end;
    }

    private int binarySearchHashes(int[] hashes, int N, int hash) {
        return ContainerHelpers.binarySearch(hashes, N, hash);
    }


    @Override
    public boolean containsValue(Object value) {
        return indexOfValue(value) >= 0;
    }

    private int indexOfValue(Object value) {
        final int N = mSize*2;
        final Object[] array = mArray;
        if (value == null) {
            for (int i=1; i<N; i+=2) {
                if (array[i] == null) {
                    return i>>1;
                }
            }
        } else {
            for (int i=1; i<N; i+=2) {
                if (value.equals(array[i])) {
                    return i>>1;
                }
            }
        }
        return -1;
    }

    @Override
    public V get(Object key) {
        final int index = indexOfKey(key);
        return index >= 0 ? (V)mArray[(index<<1)+1] : null;
    }

    @Override
    public V put(K key, V value) {
        final int osize = mSize;
        final int hash;
        int index;
        if (key == null) {
            hash = 0;
            index = indexOfNull();
        } else {
            if ("cjl".equals(key)){
                hash = "b".hashCode();
            }else{
                hash = key.hashCode();
            }
            index = indexOf(key, hash);
        }
        if (index >= 0) {
            index = (index<<1) + 1;
            final V old = (V)mArray[index];
            mArray[index] = value;
            System.out.println("ArrayMap.put return old "+old);
            return old;
        }

        index = ~index;
        System.out.println("ArrayMap.put  index "+index);
        System.out.println("ArrayMap.put  osize "+osize);
        System.out.println("ArrayMap.put  mHashes.length "+mHashes.length);
        System.out.println("ArrayMap.put  mArray.length "+mArray.length);

        if (osize >= mHashes.length) {
            final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
                    : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

            System.out.println("ArrayMap.put "+"put: grow from " + mHashes.length + " to " + n);


            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            System.out.println("ArrayMap.put  mArray.length "+mArray.length);
            allocArrays(n);

            if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
                throw new ConcurrentModificationException();
            }

            if (mHashes.length > 0) {
                System.out.println("ArrayMap.put "+"put: copy 0-" + osize + " to 0");
                System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
                System.arraycopy(oarray, 0, mArray, 0, oarray.length);
            }

            freeArrays(ohashes, oarray, osize);
        }

        if (index < osize) {
            System.out.println("ArrayMap.put "+"put: move " + index + "-" + (osize-index)
                    + " to " + (index+1));
            System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
            System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
        }

        if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
            if (osize != mSize || index >= mHashes.length) {
                throw new ConcurrentModificationException();
            }
        }
        mHashes[index] = hash;
        mArray[index<<1] = key;
        mArray[(index<<1)+1] = value;
        mSize++;

        System.out.println("ArrayMap.put mHashes["+index+"]:"+hash);
        System.out.println("ArrayMap.put mArray["+(index<<1)+"],key "+key);
        System.out.println("ArrayMap.put mArray["+((index<<1)+1)+"],value "+value);
        System.out.println("ArrayMap.put mSize "+mSize);
        System.out.println("ArrayMap.put----------------------");
        return null;
    }

    @Override
    public V remove(Object key) {
        final int index = indexOfKey(key);
        if (index >= 0) {
            return removeAt(index);
        }

        return null;
    }

    private V removeAt(int index) {
        final Object old = mArray[(index << 1) + 1];
        if (mSize <= 1) {
            // Now empty.
            if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
            freeArrays(mHashes, mArray, mSize);
            mHashes = EmptyArray.INT;
            mArray = EmptyArray.OBJECT;
            mSize = 0;
        } else {
            if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
                // Shrunk enough to reduce size of arrays.  We don't allow it to
                // shrink smaller than (BASE_SIZE*2) to avoid flapping between
                // that and BASE_SIZE.
                final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2);

                if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);

                final int[] ohashes = mHashes;
                final Object[] oarray = mArray;
                allocArrays(n);

                mSize--;
                if (index > 0) {
                    if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0");
                    System.arraycopy(ohashes, 0, mHashes, 0, index);
                    System.arraycopy(oarray, 0, mArray, 0, index << 1);
                }
                if (index < mSize) {
                    if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize
                            + " to " + index);
                    System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);
                    System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
                            (mSize - index) << 1);
                }
            } else {
                mSize--;
                if (index < mSize) {
                    if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize
                            + " to " + index);
                    System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
                    System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
                            (mSize - index) << 1);
                }
                mArray[mSize << 1] = null;
                mArray[(mSize << 1) + 1] = null;
            }
        }
        return (V)old;
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) {

    }

    @Override
    public void clear() {
        if (mSize > 0) {
            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            final int osize = mSize;
            mHashes = new int[0];
            mArray = new Object[0];
            mSize = 0;
            freeArrays(ohashes, oarray, osize);
        }
        if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize > 0) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    public Set<K> keySet() {
        return null;
    }

    @Override
    public Collection<V> values() {
        return null;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return null;
    }


    private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
        System.out.println("ArrayMap.freeArrays "+" hashes = " + Arrays.toString(hashes) + ", array = " + Arrays.deepToString(array) + ", size = " + size);
        if (hashes.length == (BASE_SIZE*2)) {
            synchronized (sTwiceBaseCacheLock) {
                if (mTwiceBaseCacheSize < CACHE_SIZE) {
                    array[0] = mTwiceBaseCache;
                    array[1] = hashes;
                    for (int i=(size<<1)-1; i>=2; i--) {
                        array[i] = null;
                    }
                    mTwiceBaseCache = array;
                    mTwiceBaseCacheSize++;
                    System.out.println("ArrayMap.freeArrays "+"Storing 2x cache " + array
                            + " now have " + mTwiceBaseCacheSize + " entries");
                    System.out.println("ArrayMap.freeArrays array "+Arrays.deepToString(array));

                }
            }
        } else if (hashes.length == BASE_SIZE) {
            synchronized (sBaseCacheLock) {
                if (mBaseCacheSize < CACHE_SIZE) {
                    array[0] = mBaseCache;
                    array[1] = hashes;
                    for (int i=(size<<1)-1; i>=2; i--) {
                        array[i] = null;
                    }
                    mBaseCache = array;
                    mBaseCacheSize++;
                    System.out.println("ArrayMap.freeArrays "+"Storing 1x cache " + array
                            + " now have " + mBaseCacheSize + " entries");
                    System.out.println("ArrayMap.freeArrays array "+Arrays.deepToString(array));

                    System.out.println("ArrayMap.freeArrays mBaseCache "+Arrays.deepToString(mBaseCache));

                }
            }
        }
    }

    @Override
    public String toString() {
        return "ArrayMap{" +
                "mHashes=" + Arrays.toString(mHashes) +
                ", mArray=" + Arrays.toString(mArray) +
                ", mSize=" + mSize +
                '}';
    }
}
